package crawler.web.other;

import java.util.ArrayList;

import org.htmlparser.Node;

public class PageDistance {

	/**
	 * 源串和目标串之间的编辑距离, 返回结果越小越相似, 2个网页
	 * 
	 * @param s
	 *            输入源串
	 * @param t
	 *            输入目标串
	 * @return 源串和目标串之间的编辑距离
	 */
	public static double LD(ArrayList<Node> s, ArrayList<Node> t) {
		int matrix[][]; // matrix
		int sLen; // length of s
		int tLen; // length of t
		int i; // iterates through s
		int j; // iterates through t
		Node nodeI; // ith character of s
		Node nodeJ; // jth character of t
		int cost; // cost

		// Step 1 initialization
		sLen = s.size();
		tLen = t.size();
		if (sLen == 0 || tLen == 0) {
			return 1;
		}

		//using dynamic programming algorithm
		matrix = new int[sLen + 1][tLen + 1];

		// Step 2 Initialize the first column to 0..n.
		for (i = 0; i <= sLen; i++)
			matrix[i][0] = i;

		//Initialize the first row to 0..m.
		for (j = 0; j <= tLen; j++)
			matrix[0][j] = j;

		// Step 3 Examine each node of s (i from 1 to n).
		// from s[0] -> s[len-1]
		for (i = 1; i <= sLen; i++) {
			nodeI = s.get(i - 1);
			// Step 4 Examine each node of t (j from 1 to m).
			for (j = 1; j <= tLen; j++) {
				nodeJ = t.get(j - 1);

				// Step 5
				//	If s[i] equals t[j], the cost is 0.
				//  If s[i] doesn't equal t[j], the cost is 1.
				if (nodeI.getClass().equals(nodeJ.getClass())) {
					cost = 0;
				} else {
					//System.out.println("diff"+s_i.toHtml()+" "+t_j.toHtml());
					cost = 1;
				}

				// Step 6
				//Set cell d[i,j] of the matrix equal to the minimum of:
				//a. The cell immediately above plus 1: d[i-1,j] + 1.
				//b. The cell immediately to the left plus 1: d[i,j-1] + 1.
				//c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
				matrix[i][j] = Minimum(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + cost);
			}
		}

		// Step 7
		//	After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].
		double ret = 0.0D;
		if (sLen > tLen) {
			ret = (double) matrix[sLen][tLen] / (double) sLen;
		} else {
			ret = (double) matrix[sLen][tLen] / (double) tLen;
		}
		return ret;
	}

	/**
	 * Get minimum of three values
	 * 
	 * @author waynechen
	 * @param a
	 * @param b
	 * @param c
	 * @return
	 */
	private static int Minimum(int a, int b, int c) {
		int mi;
		mi = a;
		if (b < mi) {
			mi = b;
		}
		if (c < mi) {
			mi = c;
		}
		return mi;
	}
}
